King's graph

King's graph
8x8 King's graph
Vertices	nm
Edges	4nm-3(n+m)+2

In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an $n \times m$ king's graph is a king's graph of an $n \times m$ chessboard.

For a $n \times m$ king's graph the total number of vertices is simply $n m$ .

For a $n \times n$ king's graph the total number of vertices is simply $n^2$ and the total number of edges is $(2n-2)(2n-1)$ . Additionally, the number of edges for various $n$ is identified as A002943 in the On-Line Encyclopedia of Integer Sequences.

Neighbourhood in the king's graph corresponds to the Moore neighborhood for cellular automata.

King's graph

See also